package sequentiell;

import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author Lukas Subel, Patrick Bender
 *
 */
public class TopMasche {

	/**
	 * List of all maschen.
	 */
	private ArrayList<Masche> topMasche;
	
	/**
	 * The highest number of masche-index; used to count if a masche was divided into 2 maschen
	 */
	private int index;

	/**
	 * Add a masche to the list of maschen.
	 * @param masche The masche to add. Check if argument is null.
	 */
	public void addMasche(Masche masche) {
		if (masche == null) throw new IllegalArgumentException("Masche darf nicht null sein bei addMasche");
		topMasche.add(masche);
	}
	
	/**
	 * Increment the index and return the new value.
	 * @return The new index.
	 */
	public int getNewIndex() {
		return ++index;
	}
	
	/**
	 * Constructor; at the end, all nodes with the same capacity are summarized to a masche,
	 * and all maschen are registered at the maschen-list
	 * @param graph A list with all the nodes of the graph.
	 */
	public TopMasche(ArrayList<Node> graph) {
		//initalize the list of maschen
		topMasche = new ArrayList<Masche>();
		//initalize a map
		HashMap<Integer, Masche> erg = new HashMap<Integer,Masche>();
		//while there are other nodes to handle
		while (graph.size() > 0) {
			//get a node from list of nodes
			Node act = graph.remove(graph.size()-1);
			//if the new capacity is bigger then the index, set the index to the bigger capacity
			if (act.getCapacity() > index) index = act.getCapacity();
			//if the map contains a masche with the same capacity
			if (erg.containsKey(act.getCapacity()))
			{
				//put the node into this masche
				Masche targetMasche = erg.get(act.getCapacity());
				targetMasche.add(act);
				act.setMasche(targetMasche);
			}
			else 
			{
				//otherwise construct a new masche and put it in there
				Masche temp = new Masche();
				temp.add(act);
				temp.setId(act.getCapacity());
				act.setMasche(temp);
				erg.put(act.getCapacity(), temp);
			}	
		}
		
		// finally, put all the generated maschen into our list of maschen
		for (Integer act : erg.keySet())
		{
			addMasche(erg.get(act));
		}
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		return topMasche.toString();
	}
	
	/**
	 * Get the number of maschen.
	 * @return The number of maschen.
	 */
	public int getSize() {
		return this.topMasche.size();
	}
	
	/**
	 * @return
	 */
	public boolean reduce() {
		//get a list with all maschen
		ArrayList<Masche> newTopMasche = new ArrayList<Masche>(this.topMasche); 
		//set a changed variable on false
		boolean changed = false;
		//iterate over all maschen
		for (Masche masche : topMasche) {
			//Masche mascheCopy = new Masche(masche);
			
			//run over all nodes of a masche, mark every predecessor
			//by writing node and linked masche into a list
			HashSet<Node> marked = new HashSet<Node>();
			HashSet<Masche> maschen = new HashSet<Masche>();
			for(Node node : masche.getMasche()) {
				for(Node act : node.getPred()) {
					marked.add(act);
					maschen.add(act.getMasche());
				}
			}
			//check for every marked masche
			for (Masche actMasche : maschen)
			{
				//if the set of marked nodes contains all nodes of a masche, do nothing
				if (marked.containsAll(actMasche.getMasche())) continue;
				else 
					{
						//otherwise, divide the masche by removing every marked node of the masche
						//and put these into a new masche
						changed = true;
						Masche temp = new Masche();
						temp.setId(this.getNewIndex());
						for(Node act : marked)
						{
							if (actMasche.remove(act)) temp.add(act);
						}
						//put the new masche into the maschen-list
						newTopMasche.add(temp);
					}
			}
			
		}
		
		topMasche = newTopMasche;
		return changed;
	}

	/**
	 * Test method; used to test if parser and Algorithm are running correctly. 
	 * @param url The location of the .xml-file.
	 * @param expected The expected restult.
	 * @throws FileNotFoundException if the .xml wasn't found.
	 * @throws Exception if the calculated result wasn't equal to the expected.
	 */
	public static int test (boolean nutzlos, int expected, String... url) throws FileNotFoundException, Exception {
		long begin = System.currentTimeMillis();
		long readTime = System.currentTimeMillis();
		HashMap<Integer,Node> graph = new HashMap<Integer,Node>();
		new Parser(url, graph).goGoGo();
		readTime = System.currentTimeMillis() - readTime;
		int i = 0;
		System.out.println("Datei: " + Arrays.deepToString(url));
		System.out.println("Schritt A: " + graph);
		TopMasche topMasche = new TopMasche(new ArrayList<Node>(graph.values()));
		System.out.println("Schritt B: " + topMasche);
		while (topMasche.reduce())  ;
		//	System.out.println("Schritt C " + ++i + ": " + topMasche);
		System.out.println("Schritt C " + ++i + ": " + topMasche);
		System.out.println("Schritt C " + ++i + ": Es gibt nichts mehr zu reduzieren");
		System.out.println("Schritt D: Es sind " + topMasche.getSize() + " Knoten");
		if (topMasche.getSize() != expected) throw new Exception("Expected " + expected + " but was " + topMasche.getSize());
		System.out.println("Schritt E: Herzlichen Glückwunsch zur Wiederwahl Frau Mörkel");
		System.out.println("Brauchte: " + (System.currentTimeMillis() - begin) + "ms, davon " + readTime + "ms zum Einlesen");
		System.out.println();
		return topMasche.getSize();
	}
	
	public static int test (String... url) throws FileNotFoundException, Exception {
		HashMap<Integer,Node> graph = new HashMap<Integer,Node>();
		new Parser(url, graph).goGoGo();
		TopMasche topMasche = new TopMasche(new ArrayList<Node>(graph.values()));
		while (topMasche.reduce())  ;
		return topMasche.getSize();
	}
	
	/**
	 * Main Method; used to start the tests with existing .xml
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {
		
		long debugtime = System.currentTimeMillis();
		long testzahl = 20000000;
		
		for (int i = 1; i <= testzahl; i++) {
			try {
				long testtime = System.currentTimeMillis();
				//int zahl = test(true,7,"testsuite/multiple/graph03_a.xml", "testsuite/multiple/graph03_b.xml", "testsuite/multiple/graph03_c.xml");
				//int zahl = test(true,1,"testsuite/spice/graph10.xml");
				//int zahl = test("C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph01_a.xml", "C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph01_b.xml");
				//int zahl = test("Milchstrasse_generated_5000.xml");
				//int zahl = test(false,501,"test-cases/500sequential_501.xml");
				//int zahl = test("test-cases/TestGraph11.xml");
				//int zahl = test("C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph05_a.xml", "C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph05_b.xml", "C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph05_c.xml", "C:\\Users\\IBKR\\Downloads\\testsuite\\multiple\\graph05_d.xml");
				int zahl = test("testsuite/crack/germany.xml");
				//int zahl = test("C:\\Users\\IBKR\\Downloads\\testsuite\\spice\\graph19.xml");
				//int zahl = test(true,4,"testsuite/speed/graph15.xml");
				//int zahl = test(false,4,"test-cases/TestGraph4.xml");
				//int zahl = test(false,8,"test-cases/Energienetz8.xml");
				//int zahl = test(false,13,"test-cases/Neuschleswegien13.xml");
				//int zahl = test("test-cases/GraphausderVorlesung_8.xml");
				System.out.println("Versuch " + i + ", " + (System.currentTimeMillis() - testtime) + "ms. Erg: " + zahl);
				}
			catch (Exception e) {
				e.printStackTrace();
				System.exit(-1); 
			}
		}
		
		System.out.println( (System.currentTimeMillis() - debugtime) + "ms fuer " + testzahl + " Versuche");
		System.out.println( ( ((System.currentTimeMillis() - debugtime) / (double)testzahl) ) + "ms im Durchschnitt");
	}
	
}

